﻿#region Copyright information
// 
// Copyright © 2005-2013 Yongkee Cho. All rights reserved.
// 
// This code is a part of the Biological Object Library and governed under the terms of the
// GNU Lesser General  Public License (LGPL) version 2.1 which accompanies this distribution.
// For more information on the LGPL, please visit http://bol.codeplex.com/license.
// 
// - Filename: GeneticAlgorithmBase.cs
// - Author: Yongkee Cho
// - Email: yongkeecho@gmail.com
// - Date Created: 2012-12-08 8:26 AM
// - Last Modified: 2013-01-25 3:59 PM
// 
#endregion
using System;
using System.Collections.Generic;
using System.Linq;
using BOL.Linq;

namespace BOL.Algorithms.Optimization.EvolutionaryAlgorithms
{
    public abstract class GeneticAlgorithmBase<TGene, TPhenome> : AlgorithmBase
    {
        #region Private variables

        private readonly Random _random;
        private readonly bool _doParallel;
        private readonly int _k = -1;
        private readonly bool _allowRedundancyInPopulation;
        private List<IGenome<TGene>> _populationOrderedByDescendingFitness;

        #endregion

        #region Public properties

        public int I { get; private set; }

        public IGenome<TGene> Seed { get; private set; }
        
        public List<IGenome<TGene>> Population { get; set; }
        
        public List<IGenome<TGene>> Elites { get; private set; }

        /// <sumary>Gets or sets the size of population.</sumary>
        public int PopulationSize { get; private set; }

        /// <sumary>Gets or sets the number of elites to survive in the next generation.</sumary>
        public int NumberOfElites { get; private set; }

        /// <sumary>Gets or sets the selection method.</sumary>
        public SelectionMethod SelectionMethod { get; private set; }

        /// <sumary>Gets or sets the crossover rate.</sumary>
        public double CrossoverRate { get; private set; }

        /// <sumary>Gets or sets the mutation rate.</sumary>
        public double MutationRate { get; private set; }

        /// <sumary>Gets or sets the number of generations.</sumary>
        public int NumberOfGenerations { get; set; }

        /// <sumary>Gets or sets the tolerances.</sumary>
        public double Tolerance { get; private set; }

        /// <summary>Gets or sets if the algorithm will print to the console or not.</summary>
        public bool IsVerbose { get; private set; }

        #endregion

        #region Constructors

        protected GeneticAlgorithmBase(Random random, IGenome<TGene> seed, int populationSize, int numberOfElites, SelectionMethod selectionMethod, double crossoverRate, double mutationRate, int numberOfGenerations, bool allowRedundancyInPopulation, double tolerance = 1E-10, bool isVerbose = false, bool doParallel = false)
        {
            if (seed == null)
                throw new ArgumentNullException("seed", "Seed is null.");

            if ((populationSize - numberOfElites) < 2 || populationSize < 2)
                throw new ArgumentOutOfRangeException(null, "Bad population size or number of elites.");

            if (crossoverRate < 0 || crossoverRate > 1)
                throw new ArgumentOutOfRangeException("crossoverRate", "Crossover rate should be between 0 and 1.");

            if (mutationRate < 0 || mutationRate > 1)
                throw new ArgumentOutOfRangeException("mutationRate", "Mutation rate should be between 0 and 1.");

            _random = random;
            Seed = seed;
            PopulationSize = populationSize;
            NumberOfElites = numberOfElites;
            SelectionMethod = selectionMethod;
            CrossoverRate = crossoverRate;
            MutationRate = mutationRate;
            NumberOfGenerations = numberOfGenerations;
            _allowRedundancyInPopulation = allowRedundancyInPopulation;
            Tolerance = tolerance;
            IsVerbose = isVerbose;
            _doParallel = doParallel;

            if (isVerbose)
            {
                Console.WriteLine("=====================================================");
                Console.WriteLine(" Genetic Algorithm");
                Console.WriteLine("=====================================================");
                Console.WriteLine("   - population size: {0}", populationSize);
                Console.WriteLine("   - selection method: {0}", selectionMethod);
                if (selectionMethod != SelectionMethod.SteadyState)
                    Console.WriteLine("   - number of elites: {0}", numberOfElites);
                Console.WriteLine("   - crossover rate: {0}", crossoverRate);
                Console.WriteLine("   - mutation rate: {0}", mutationRate);
                if (selectionMethod != SelectionMethod.SteadyState)
                    Console.WriteLine("   - number of generations: {0}", numberOfGenerations);
                Console.WriteLine("   - tolerance: {0}", tolerance);
            }
        }

        // tournament selection
        protected GeneticAlgorithmBase(Random r, IGenome<TGene> seed, int populationSize, int numberOfElites, int k, double crossoverRate, double mutationRate, int numberOfGenerations, bool allowRedundancyInPopulation, double tolerance = 1E-10, bool isVerbose = false, bool doParallel = false)
            : this(r, seed, populationSize, numberOfElites, SelectionMethod.Tournament, crossoverRate, mutationRate, numberOfGenerations, allowRedundancyInPopulation, tolerance, isVerbose, doParallel)
        {
            if (k < 0 || k > populationSize)
                throw new ArgumentOutOfRangeException("k", "k should be greater than 0 and smaller than population size.");
            
            _k = k;
        }

        // steady-state selection
        protected GeneticAlgorithmBase(Random r, IGenome<TGene> seed, int populationSize, double crossoverRate, double mutationRate, bool allowRedundancyInPopulation, double tolerance = 1E-10, bool isVerbose = false, bool doParallel = false)
            : this(r, seed, populationSize, populationSize - 2, SelectionMethod.SteadyState, crossoverRate, mutationRate, Int32.MaxValue, allowRedundancyInPopulation, tolerance, isVerbose, doParallel) { }

        #endregion

        #region public methods
        
        protected virtual bool Optimize()
        {
            // Start performance counter
            Stopwatch.Start();

            InitializePopulation();

            I = 0;

            if (IsVerbose)
                Console.WriteLine("\n[Optimization]");

            do
            {
                // evaluates fitness of chromosomes in the population
                Population.ForEach(x => x.Evaluate());
                _populationOrderedByDescendingFitness = _doParallel
                                                            ? Population.AsParallel().OrderByDescending(x => x.Fitness).
                                                                  ToList()
                                                            : Population.OrderByDescending(x => x.Fitness).ToList();

                List<IGenome<TGene>> newPopulation;
                if (NumberOfElites > 0)
                {
                    Elites = _populationOrderedByDescendingFitness.Take(NumberOfElites).ToList();
                    newPopulation = new List<IGenome<TGene>>(Elites);

                    //if (IsVerbose)
                    //    Console.WriteLine(" - Generation {0} : elapsed = {1}, avg fitness = {2:G4}", I++,
                    //                      Stopwatch.ElapsedTicks, Elites.Average(x => x.Fitness));
                }
                else
                {
                    newPopulation = new List<IGenome<TGene>>();

                    //if (IsVerbose)
                    //    Console.WriteLine(" - Generation {0} : elapsed = {1}, avg fitness = {2:G4}", I++,
                    //                      Stopwatch.ElapsedTicks, Population.Average(x => x.Fitness));
                }
                Console.WriteLine(" - Generation {0} : Best fitness = {1:G4}", I++, _populationOrderedByDescendingFitness.First().Fitness);


                while (newPopulation.Count < PopulationSize)
                {
                    IGenome<TGene> dadCopy, momCopy;

                    // Selection
                    Select(out dadCopy, out momCopy);

                    // Crossover
                    if (_random.NextDouble() <= CrossoverRate)
                        dadCopy.Crossover(momCopy);

                    // Mutation
                    dadCopy.Mutate(MutationRate);
                    momCopy.Mutate(MutationRate);

                    if (IsAcceptable(newPopulation, dadCopy))
                        newPopulation.Add(dadCopy);
                    if (IsAcceptable(newPopulation, momCopy))
                        newPopulation.Add(momCopy);
                }

                if (!IsConverged())
                    Population = newPopulation;
                else
                    break;

            }
            #if !(SILVERLIGHT || WINDOWS_PHONE)
            while (!Console.KeyAvailable || Console.ReadKey(true).Key != ConsoleKey.Escape);
            #else
            while (true);
            #endif

            Stopwatch.Stop();

            return true;
        }

        public virtual IEnumerable<TPhenome> Optimize(int count)
        {
            if (NumberOfElites > 0)
                if (0 > count || count > NumberOfElites)
                    throw new ArgumentOutOfRangeException("count");

            if (Optimize()) // if optimized, returns the n best phenotypes
            {
                var result = Population.Where(x => !IsAcceptable(Population, x)).OrderByDescending(g => g.Fitness).Take(count).ToList();
                
                if (IsVerbose)
                {
                    Console.WriteLine("\n[Termination]");
                    Console.WriteLine(" : {0} unique phenomes was successfully generated.", result.Count);
                    Console.WriteLine("\nTime elapsed : {0}", ElapsedTime);
                }

                return result.Select(Decode);
            }
            
            return null;
        }

        protected abstract TPhenome Decode(IGenome<TGene> genome);  

        #endregion

        #region Protected methods

        protected virtual void InitializePopulation()
        {
            if (IsVerbose)
                Console.WriteLine("\n[Initialization]");

            // Initializes current population
            Population = new List<IGenome<TGene>>();
            while (Population.Count < PopulationSize)
            {
                var offspring = Seed.Offspring();

                if (IsAcceptable(Population, offspring))
                    Population.Add(offspring);
            }

            if (IsVerbose)
                Console.WriteLine(" : {0} genomes were successfully generated.", PopulationSize);
        }


        #region Selection methods

        private IGenome<TGene> RouletteWheelSelect(double f)
        {
            // generate random numbers from [0, f)
            var r = _random.NextDouble() * f;
            var sum = 0.0;

            return _populationOrderedByDescendingFitness.First(genome =>
            {
                sum += genome.Fitness;
                return sum > r;
            });
        }

        private IGenome<TGene> StochasticUniversalSamplingSelect(double f)
        {
            // generate random numbers from [0, f/N)
            var fOverN = f / PopulationSize;
            var r = _random.NextDouble() * fOverN;
            var max = Enumerable.Range(0, PopulationSize).Last(i =>
            {
                r += fOverN;
                return r < f;
            });

            r = _random.NextDouble() * fOverN + _random.Next(0, max) * fOverN;
            var sum = 0.0;
            return _populationOrderedByDescendingFitness.First(genome =>
            {
                sum += genome.Fitness;
                return sum > r;
            });
        }

        private IGenome<TGene> RankSelect(int s)
        {
            // generate random numbers from [1, s)
            var r = _random.Next(1, s); 
            var sum = 0.0;
            var i = PopulationSize;

            return _populationOrderedByDescendingFitness.First(genome =>
            {
                sum += i--;
                return sum >= r;
            });
        }

        #endregion

        protected virtual void Select(out IGenome<TGene> dadCopy, out IGenome<TGene> momCopy)
        {
            switch (SelectionMethod)
            {
                case SelectionMethod.RouletteWheel:
                    {
                        // sum of fitness in population
                        var f = Population.Sum(g => g.Fitness);

                        dadCopy = RouletteWheelSelect(f);
                        do { momCopy = RouletteWheelSelect(f); } while (dadCopy.Equals(momCopy));

                        dadCopy = dadCopy.Clone() as IGenome<TGene>;
                        momCopy = momCopy.Clone() as IGenome<TGene>;
                    }
                    break;
                case SelectionMethod.StochasticUniversalSampling:
                    {
                        // sum of fitness in population
                        var f = Population.Sum(g => g.Fitness);

                        dadCopy = StochasticUniversalSamplingSelect(f);
                        do { momCopy = StochasticUniversalSamplingSelect(f); } while (dadCopy.Equals(momCopy));

                        dadCopy = dadCopy.Clone() as IGenome<TGene>;
                        momCopy = momCopy.Clone() as IGenome<TGene>;
                    }
                    break;
                case SelectionMethod.Rank:
                    {
                        // triangular number T(N) = n * (n + 1) / 2
                        var T = PopulationSize * (PopulationSize + 1) / 2;

                        dadCopy = RankSelect(T);
                        do { momCopy = RankSelect(T); } while (dadCopy.Equals(momCopy));

                        dadCopy = dadCopy.Clone() as IGenome<TGene>;
                        momCopy = momCopy.Clone() as IGenome<TGene>;
                    }
                    break;
                case SelectionMethod.Tournament:
                    {
                        var parent = Population.OrderByRandom(_random).Take(_k).OrderByDescending(g => g.Fitness).Take(2).ToArray();
                        dadCopy = parent[0].Clone() as IGenome<TGene>;
                        momCopy = parent[1].Clone() as IGenome<TGene>;
                    }
                    break;
                case SelectionMethod.SteadyState:
                    {
                        var parent = _populationOrderedByDescendingFitness.Take(2).ToArray();
                        dadCopy = parent[0].Clone() as IGenome<TGene>;
                        momCopy = parent[1].Clone() as IGenome<TGene>;
                    }
                    break;
                default:
                    throw new Exception("Implement your own selection function.");
            }
        }

        protected virtual bool IsAcceptable(List<IGenome<TGene>> population, IGenome<TGene> genome)
        {
            if (!_allowRedundancyInPopulation)
            {
                if (_doParallel)
                    return !population.AsParallel().Contains(genome);

                return !population.Contains(genome);
            }

            return true;
        }

        protected abstract bool IsConverged();

        #endregion
    }
}
